package com.explorati.LeetCode047.permuteUnique;

import com.explorati.MaxHeap.Array;
import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 19:02 2020/10/4 0004
 * @ Description ：
 */
public class Solution1 {

    //当前位置元素是否被使用过
    boolean[] used;
    //返回结果集
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums.length == 0) {
            return res;
        }
        used = new boolean[nums.length];

        //排序
        Arrays.sort(nums);
        generatePermutation(nums, 0, new ArrayList<>());
        return res;
    }

    private void generatePermutation(int[] nums, int index, List<Integer> preList) {
        // 也可以
//        if(preList.size() == nums.length) {
        if(index == nums.length) {
            res.add(new ArrayList<>(preList));
            return ;
        }

        for(int i = 0; i < nums.length; i++) {
            //如果当前元素被使用过 或者 （当前元素和前一个元素值相等 并且 前一个元素没有被使用过） continue
            if(used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            preList.add(nums[i]);
            used[i] = true;
            generatePermutation(nums, index + 1, preList);
//            preList.remove(index);
            preList.remove(preList.size() - 1);
            used[i] = false;
        }
    }
}
